This disclosure relates generally to problem solution approaches and more particularly to solution evaluation utilizing computation time balanced against solution quality.
Many tasks, such as paper path planning, parsing, or biological sequence alignment, can be thought of as finding the shortest path between an initial state and a goal state in a large graph. Various methods for finding optimal solutions are known in the art, and various ad-hoc methods have been proposed to quickly find sub-optimal solutions, represented as shortest-path problems. If sufficient computation is available, optimal solutions to such problems can be found using A* search with an admissible heuristic (Peter E. Hart, Nils J. Nilsson, and Bertram Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”, IEEE Transactions of Systems Science and Cybernetics, SSC-4(2):100-107, July 1968). However, in many practical scenarios, time is limited or costly and it is not desirable, or even feasible, to look for the least-cost path. Instead, search effort must be carefully allocated in a way that balances the cost of the paths found with the cost of the computation and the amount of time available.
By way of example, A* is a best-first search in which the ‘open list’ of unexplored nodes is sorted by f(n)=g(n)+h(n), where g(n) denotes the known cost of reaching a node n from the initial state and h(n) is typically a lower bound on the cost of reaching a solution from n. A* is optimal in the sense that no algorithm that returns an optimal solution using the same lower bound function h(n) visits fewer nodes (Rina Dechter and Judea Pearl, “The Optimality of A*”, in Laveen Kanal and Vipin Kumarto, editors, Search in Artificial Intelligence, pages 166-199, Springer-Verlag, 1988). However, in many applications solutions are needed faster than A* can provide them. To find a solution faster, it is common practice to increase the weight of h(n) via f(n)=g(n)+w·h(n), with w≧1. There are many variants of weighted A* search, including Anytime A* and ARA*. In ARA*, for example, a series of solutions of decreasing cost is returned over time. The weight w is initially set to a high value and then decremented by δ after each solution. If allowed to continue, w eventually reaches 1 and the cheapest path is discovered. Of course, finding the optimal solution this way takes longer than simply running A* directly.
These algorithms suffer from two inherent difficulties. First, it is not well understood how to set parameters to best satisfy the user's needs. Setting ω too high or δ too low can result in many poor-quality solutions being returned, wasting time. But if ω is set too low or δ too high, the algorithm may take a very long time to find a solution. Therefore, to use a weighted A* technique like ARA* the user must perform many pilot experiments in each new problem domain to find good parameter settings.
Second, for anytime algorithms such as ARA*, the user must estimate the right time to stop the algorithm. The search process appears as a black box that could emit a significantly better solution at any moment, so the user must repeatedly estimate the probability that continuing the computation will be worthwhile. This requires substantial prior statistical knowledge of the run-time performance profile of the algorithm and rests on the assumption that such learned knowledge applies to the current instance.
These difficulties suffer from a more general problem: anytime algorithms must provide suboptimal performance due to their ignorance of the user's utility function. It is simply not possible in general for an algorithm to quickly transform the best solution achievable starting from nothing within time t into the best solution achievable in time t+1. Without the ability to decide during the search whether a distant solution is worth the effort of reaching it, anytime algorithms must either waste time finding nearby poor-quality solutions or overexert themselves finding the very best solution when any would have sufficed.
It would be desirable to eliminate the problems of ad hoc parameter modification and laborious performance profiling by applying an estimate of the distance in search steps to the nearest solution below a search node and combining this with the user's utility function to evaluate candidate search nodes.